1. Field of the Invention
The present invention generally relates to computer implementable decision support systems for determining a production schedule of feasible material releases within a complex multi-stage manufacturing system architecture. In more particularity, the present invention relates to a system for rationing manufacturing resources among competing demands according to a defined set of business rules.
2. Background Description
The manufacturing of semiconductors is a complex and refined process. This process includes everything from growing silicon crystals, to the actual placement and soldering of chips to a printed circuit board. Initially, raw wafers are cut from a silicon ingot and processed through a specific sequence of work centers. The end goal of this process is to build a set of integrated circuits on the surface of the silicon wafer according to a specific circuit design. This process involves repeatedly applying four basic steps: deposition, photolithography, etching, and ion implantation. These steps are the means by which materials with specific dielectric properties (e.g., conductors, insulators) are deposited on the surface of the wafer according to the precise circuit design specifications. These steps are repeated many times to build up several layers (typically between 12 and 25 layers) of the circuits.
After the circuits have been built on the wafers they are tested to determine the resultant yield of operational circuits and tagged for later reference. The circuits are then diced and sorted, and subsequently wire bonded to a substrate to assemble a module. These modules, which are further tested to determine electromagnetic and thermal characteristics, are eventually combined on printed circuit boards to form cards. Finally, the cards are tested and those that pass are eventually used in the assembly of a wide range of finished electronic products (e.g., personal computers, printers, CD players, etc.). From the point of view of semiconductor manufacturing, the modules and cards are, mostly, the finished products taken to market.
To assemble the modules and cards (or other end products), a Bill of Material (BOM) is needed to specify the required components used in the assembly of each particular part number (PN) produced within the manufacturing system. The BOM can be used to generate a graphical representation of the stages within a manufacturing process for each of the finished products. For example, FIG. 1 shows a high level block diagram of the BOM for semiconductor manufacturing which can be broken into the following four aggregate stages: wafer stage 110, device/substrate stage 120, module stage 130, and card stage 140. These aggregate stages may involve many steps each of which may significantly impact the flow of materials through the manufacturing system. For example, the wafer stage 110 may involve wafer fabrication involving many passes through photolithography work centers to build multiple levels of a circuit structure. The dicing of the silicon wafer stage 120 involves a single item in the production process which is then converted into different devices. Also, the card stage 140 may involve the assembly of many devices to generate a single card. These stages result in multiple qualities of items being output from various stages of the manufacturing system according to a known distribution.
In addition to the BOM, other sources of manufacturing information such as yields, cycle times, shipping routes, etc. are critical for advance planning and scheduling of the product. However, a fundamental problem faced in all manufacturing industries is the matching of demand and assets over a set time period. By way of example, production lead times necessitate the advance planning of production so that material releases throughout the production system are coordinated with the end customers demand for any of a wide range of finished products (typically on the order of thousands in semiconductor manufacturing). Such advance planning depends on the availability of finite resources which include, for example, finished goods inventory, work in process (WIP) at various stages of the manufacturing system, and work center capacity. Furthermore, there may be multiple locations, processes, and work centers that may be utilized for a particular job.
As is known, product advance planning decisions are necessary due to the complicated process architecture and unavoidably long lead times to complete processing through all manufacturing stages for a finished product. For this reason and to accommodate the planning and scheduling functions within the semiconductor manufacturing industry, a tiered planning system was devised. The following is a summary based on the tier system devised by Sullivan, G. and Fordyce, K., 1990, “IBM Burlington's Logistics Management System”, Interfaces, 20, 1, 43–64. In this tiered system each tier is defined by the time frame to which the decisions pertains.                Tier 1: Long range (3 months to 7 yr) strategic level decisions such as mergers, capacity acquisition, major process changes, new product development, and long term policy based decisions.        Tier 2: Medium range (1 week to 6 months) tactical scheduling involving yield and cycle time estimation, forecasting and demand management, material release planning and maintenance scheduling.        Tier 3: Short to medium range (weekly planning) operational scheduling for optimizing consumption and allocation of resources and output of product, demand prioritization techniques, capacity reservation and inventory replenishment.        Tier 4: Short range (daily) dispatch scheduling for addressing issues such as machine setups, lot expiration, prioritizing of late lots, job sequencing, absorbing unplanned maintenance requirements and assigning personnel to machines.        
The above taxonomy of planning and scheduling decisions is a hierarchical one, i.e., decisions in higher tiers affect lower tiers. For example, long range capacity acquisition decisions determine eventual yield and cycle times, the available resources that can be utilized, and the extent to which maintenance is to be scheduled in the future. As is known, decisions in higher tiers, by the nature of their long time frames, are made under considerable uncertainty and thus seek to anticipate future requirements based on current information. On the other hand, lower level tier decisions are of a corrective/ reactive nature and act to absorb uncertainty not accounted for in the higher tiers. It is also noted that advanced production planning and scheduling decision support systems are typically run on a weekly basis; however, the planning horizon for such runs may range several years depending on the planning horizon of interest and the level of detail in forecasting. Thus, advance planning systems may impact decisions in tiers 1, 2 and 3 which, in turn, may affect tier 4 decisions. Therefore, the matching of assets to demand is a major planning activity which affects decisions within all tiers.
It is noted that if unlimited assets were available then the matching of demand with assets would be straightforward. In reality, however, finite supply and capacity create constraints on production scheduling. These constraints make the determination of a feasible production schedule (let alone an optimal one) a complex problem. The production scheduling, which includes major activities involved in the production planning process, can be divided into three categories: Supply Aggregation (SA), Materials Requirements Panning (MRP) and Resource Allocation (RA).
Supply Aggregation (SA)
The Supply Aggregation involves capturing and transforming micro/factory floor details into a manageable data set. For example, WIP at a particular work center in the manufacturing system may ultimately travel through a variety of different routings. These routings depend on which type of finished product is eventually produced by the WIP. However, at any given point in the system a set of operations can be isolated which are common to all potential routings that the WIP can travel through from that point forward. In other words, a limited set of the immediate future operations required for the WIP are known.
The purpose of the Supply Aggregation step is then to project the WIP forward through the required work centers to points at which decisions regarding alternative routings are necessary. As the WIP is moved forward, its amount is adjusted for yield losses at the work centers through which it has traveled. Furthermore, the time at which the WIP becomes available at the projected work center is computed based on known cycle times at each work center. In reality, these times occur over a continuum; however, in practice, these times are discretized into a finite set of time periods. The end result of the Supply Aggregation is then to significantly reduce the number of material release points considered in future calculations which, in turn, decreases computation time to compute a feasible production schedule.
Material Requirements Planning (MRP)
Material Requirements Planning is a well known production scheduling method based on “explosion” of finished product demand using manufacturing information such as the BOM, yield and cycle times, inventory and planned receipts. The MRP is based on taking demand for finished product and sequentially moving backwards through the BOM (exploding). Required material releases are determined as well as the ideal release date based on cycle times at each work center at each level of the BOM.
Specialized process dependent factors in semiconductor manufacturing introduce additional complexities beyond those that can be readily handled by basic MRP. These additional complexities may result from material substitution or binning, both of which must be accounted for in computing production schedules. For example, at certain stages of the manufacturing process there is the opportunity for material substitution in which higher quality items are substituted for lower quality items (e.g., 900 MHz processor substituted in place of a 700 MHz processor). Another important process specific to semiconductor manufacturing is binning which refers to a distribution of quality levels for circuits built on a silicon wafer. The effect of binning is to link decisions about material releases among multiple PNs within the BOM which subsequently requires the use of large scale optimization methods, typically linear programming (LP) based models. The production scheduling system which incorporates LP in generating material releases to account for binning and material substitutions is referred to as Advanced Material Requirements Planning (AMRP). See, U.S. Pat. No. 5,943,484, which is incorporated herein by reference in the entirety.
Resource Allocation (RA)
MRP generates a set of ideal material releases under the assumption that unlimited resources are available. The purpose of Resource Allocation is then to systematically adjust this ideal set of releases to make them feasible with respect to constraints due to limited resources. That is, RA is concerned with the allocation of limited capacity to generate a feasible production schedule.
Historically a broader group of methodologies, referred to as extended MRP or MRP II, have included steps in which capacity requirements are evaluated based on releases generated by MRP. A method called “Best Can Do” (BCD) (see, U.S. Pat. No. 5, 971,585), which uses linear programming, extends the capability of MRP II based systems from analysis to the actual development of a near optimal production schedule. This involves moving up from lower to higher levels of the BOM (implosion) and allocating resources sequentially at each level based on a priority ranking of the MRP material releases (which are, in turn, determined by priority ranking of orders they support). The resources allocated, using these systems, can be separated into two groups, supply and capacity. The fundamental difference between these two types of assets (groups) is that unapplied supply is available to apply at a later period; whereas, unapplied capacity is not available to apply at a later period. When supply and/or capacity constraints are violated by the MRP releases, the schedule of releases is adjusted in time by moving a portion of the release to an earlier period if possible and otherwise a sufficiently later period in time such that the required supply and capacity are available.
Plans generated using MRP are often referred to as ideal plans since they are uncapacitated (they assume unlimited supply and capacity). With this said, various rough-cut capacity planning methods have been documented in the literature (“Factory Physics: Foundations of Manufacturing Management”, Hopp, W. J., Spearman M. L., 1996, Irwin, Chicago). The nature of these methods is to determine when capacity constraints are violated rather than how to generate a feasible schedule. Detailed capacitated material release scheduling has been less explored.
Methods for achieving detailed capacitated material releases can be broadly separated into optimization based methods and heuristics. Yield losses, material substitution, and binning are examples of processes which force the use of new and specialized methods for RA typically involving the use of LP models.
A critical weakness of the priority ranking based heuristics upon which the above logic is based is the inadequacy to account for ties in ranking when rationing of resources is necessary. This is a fundamental problem faced in many industries. As mentioned, BCD relies heavily on LP based models, and rationing of resources is something which cannot be captured in LP models because it violates the underlying axioms. (LP models, by assumption, have linear objective functions and linear constraints.) As is known, LP used in BCD is formulated as a cost minimization problem where the objective function is comprised of costs for processing, shipping, back ordering, inventory holding, and material substitution, as well as negative revenues, all of which are linear in their respective decision variables. Logically, material releases of equal priority have equal cost penalties and revenues associated with rationing resources under such conditions. As a result, the allocation of resources to a particular material release can be an “all” or “nothing” scenario. This occurs because LP models exhibit degeneracy when there are multiple allocation options, i.e., multiple solutions with the same objective function value.
As a result of the above shortcomings, more complex nonlinear optimization models, or heuristics based on decision rules, are necessary to implement fair sharing of resources. The former possibility, although theoretically possible, has associated practical problems. That is, the complex nonlinear optimization models require implementing algorithms with running times significantly greater than those of LP algorithms. Thus, as of yet and in the foreseeable future, the complex models are infeasible for solving large-scale production scheduling problems in the semiconductor manufacturing industry and other industries with similarly complex manufacturing system architectures.